package 题目集.树.树链剖分;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * 代码没有问题，但java日常爆栈
 * 测试：https://www.luogu.com.cn/problem/P3384
 * 视频讲解：https://www.bilibili.com/video/BV1Qt411u77f/?spm_id_from=333.788.top_right_bar_window_history.content.click&vd_source=4c11120a0014a7c6d278add85fbdd1fc
 * 这个思路有一点妙。我们把树的dfs序，看作节点在一个线线性数组中的下标。那么我们操作对树进行的操作，是不是就可以看作对数组的操作？
 * 并且dfs序有一些性质。 父亲到孩子的顺序是有序的
 * <p>
 * 推荐先看树剖LCA
 * 树链剖分：通过将树划分为多条树干，其中越接近根的树干越粗（长度越大）。求路径中的和，相当于路径中求所有树干的和。而树干的dfs序的是线性的，可以通过线段树维护。
 */
public class ch01_树链剖分模板 {
    static int maxn = (int) (1e5 + 10);

    static Chain[] chains = new Chain[maxn];
    //dfs序下的节点权值
//    static int[] fa=new int[maxn];
//    static int[] deep=new int[maxn];
//    static int[] size=new int[maxn];
//    static int[] son=new int[maxn];
//    static int[] dfn=new int[maxn];
//    static int[] top=new int[maxn];
    static int[] dfw = new int[maxn];
    static int dfi;
    static Tree[] tree;
    static List<Integer>[] graph;
    static int n, m, root;
    static long mod;

    public static void main(String[] args) {
        Reader2 sc = new Reader2();
        n = sc.nextInt();
        m = sc.nextInt();
        root = sc.nextInt();
        mod = sc.nextLong();
        int tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(n) / Math.log(2)));
        tree = new Tree[tn];
        graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt();
            chains[i] = new Chain(v);
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        buildSize(root, root);
        buildChain(root, root);
        buildTree(1, 1, n);

        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            if (op == 1) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                long val = sc.nextLong();
                addPath(u, v, val);
            } else if (op == 2) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                long ans = queryPath(u, v);
                Reader2.pw.println(ans);
            } else if (op == 3) {
                int root = sc.nextInt();
                long val = sc.nextLong();
                addRoot(root, val);
            } else {
                int root = sc.nextInt();
                long ans = queryRoot(root);
                Reader2.pw.println(ans);
            }
        }
        Reader2.pw.flush();
    }

    public static void addPath(int high, int low, long val) {
        while (chains[high].top != chains[low].top) {
            if (chains[chains[low].top].deep < chains[chains[high].top].deep) {
                low = low ^ high;
                high = low ^ high;
                low = low ^ high;
            }
            add(1, chains[chains[low].top].dfi, chains[low].dfi, val);
            low = chains[chains[low].top].fa;
        }
        if (chains[high].deep < chains[low].deep) {
            add(1, chains[high].dfi, chains[low].dfi, val);
        } else {
            add(1, chains[low].dfi, chains[high].dfi, val);
        }
    }

    public static long queryPath(int high, int low) {
        long ans = 0;
        while (chains[high].top != chains[low].top) {
            if (chains[chains[low].top].deep < chains[chains[high].top].deep) {
                low = low ^ high;
                high = low ^ high;
                low = low ^ high;
            }
            ans += query(1, chains[chains[low].top].dfi, chains[low].dfi);
            low = chains[chains[low].top].fa;
        }
        if (chains[high].deep < chains[low].deep) {
            ans += query(1, chains[high].dfi, chains[low].dfi);
        } else {
            ans += query(1, chains[low].dfi, chains[high].dfi);
        }
        return ans % mod;
    }


    public static void addRoot(int root, long val) {
        //size包括自身
        add(1, chains[root].dfi, chains[root].dfi + chains[root].size - 1, val);
    }

    public static long queryRoot(int root) {
        return query(1, chains[root].dfi, chains[root].dfi + chains[root].size - 1);
    }

    public static void query(int root, long v) {
        add(1, chains[root].dfi, chains[root].dfi + chains[root].size, v);
    }

    public static void add(int i, int l, int r, long v) {
        if (l <= tree[i].l && tree[i].r <= r) {
            tree[i].lazy(v);
        } else {
            push(i);
            int tm = tree[i].l + tree[i].r >> 1;
            if (l <= tm) add(i << 1, l, r, v);
            if (tm < r) add(i << 1 | 1, l, r, v);
            pull(i);
        }
    }

    public static long query(int i, int l, int r) {
        if (l <= tree[i].l && tree[i].r <= r) return tree[i].sum % mod;
        push(i);
        int tm = tree[i].l + tree[i].r >> 1;
        long ans = 0;
        if (l <= tm) ans += query(i << 1, l, r);
        if (tm < r) ans += query(i << 1 | 1, l, r);
        return ans % mod;
    }

    private static void pull(int i) {
        tree[i].sum = (tree[i << 1].sum + tree[i << 1 | 1].sum) % mod;
    }

    private static void push(int i) {
        if (tree[i].lazy != 0) {
            tree[i << 1].lazy(tree[i].lazy);
            tree[i << 1 | 1].lazy(tree[i].lazy);
            tree[i].lazy = 0;
        }
    }

    private static void buildTree(int i, int l, int r) {
        tree[i] = new Tree(l, r);
        if (l == r) {
            tree[i].sum = dfw[l];
            return;
        }
        int m = l + r >> 1;
        buildTree(i << 1, l, m);
        buildTree(i << 1 | 1, m + 1, r);
        pull(i);
    }

    public static void buildChain(int u, int top) {
        chains[u].dfi = ++dfi;
        chains[u].top = top;
        dfw[dfi] = chains[u].v;
        if (chains[u].size == 1) {
            return;
        }
        buildChain(chains[u].son, top);
        for (int v : graph[u]) {
            if (v == chains[u].fa || v == chains[u].son) continue;
            buildChain(v, v);
        }
    }

    /**
     * 构建
     */
    public static void buildSize(int u, int fa) {
        chains[u].fa = fa;
        chains[u].deep = chains[fa].deep + 1;
        chains[u].size = 1;
        int maxsiz = 0;
        for (int v : graph[u]) {
            if (v == fa) continue;
            buildSize(v, u);
            chains[u].size += chains[v].size;
            if (chains[v].size > maxsiz) {
                chains[u].son = v;
                maxsiz = chains[v].size;
            }
        }
    }

    //树链信息
    static class Chain {
        //父亲，深度
        int fa, deep;
        //子树大小，重儿子
        int size, son;
        //链的头部
        int top;
        //dfs序下标
        int dfi;
        //节点值
        int v;

        public Chain(int v) {
            this.v = v;
        }

        @Override
        public String toString() {
            return "Chain{" +
                    "fa=" + fa +
                    ", deep=" + deep +
                    ", size=" + size +
                    ", son=" + son +
                    ", top=" + top +
                    ", dfi=" + dfi +
                    ", v=" + v +
                    '}';
        }
    }

    //线段树
    static class Tree {
        int l, r, len;
        long sum, lazy;

        public Tree(int l, int r) {
            this.l = l;
            this.r = r;
            len = r - l + 1;
        }

        public void lazy(long v) {
            sum += (v * len) % mod;
            lazy += v;
        }
    }

    static class Reader2 {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        public Reader2(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }

        public long nextLong() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (long) in.nval;
        }
    }
}
